package com.gitee.swsk33.algorithms.lineartable.linkedlist.singlelinkedlist;

/**
 * 单链表类
 */
public class SingleLinkedList<T> {

	/**
	 * 表示该单链表的头，链表头是链表索引的开始，其不存放内容，可以理解为头结点是一个链表的标识
	 */
	private Node<T> head;

	/**
	 * 构造函数初始化单链表对象
	 */
	public SingleLinkedList() {
		// 实例化链表头
		head = new Node<>();
	}

	/**
	 * 在链表尾部插入一个元素
	 *
	 * @param data 元素值
	 */
	public void add(T data) {
		// 从头开始往后遍历，当遍历到某个节点后面为null是说明这是最后一个节点
		Node<T> node = head;
		while (node.getNext() != null) {
			node = node.getNext();
		}
		// 这时node的下一个是空的了，就实例化一个节点加进去
		Node<T> newNode = new Node<>();
		newNode.setData(data);
		node.setNext(newNode);
	}

	/**
	 * 在指定索引处插入元素
	 *
	 * @param index 索引，0表示第一个元素（头结点的后一个）
	 * @param data  元素值
	 */
	public void insert(int index, T data) throws Exception {
		// 建立一个引用先索引到index - 1处
		Node<T> node = head;
		// 可以把头节点理解为第-1个节点（第一个节点索引是0）
		for (int i = -1; i < index - 1; i++) {
			node = node.getNext();
			// 判断是否越界
			if (node == null) {
				throw new Exception("插入位置超出范围！");
			}
		}
		// 这个时候node已经引用到了第index - 1处了
		// 先实例化新节点
		Node<T> newNode = new Node<>();
		newNode.setData(data);
		// 先让新节点的下一个指向node的下一个
		newNode.setNext(node.getNext());
		// 再让node的下一个指向新节点
		node.setNext(newNode);
	}

	/**
	 * 删除一个节点
	 *
	 * @param index 删除节点的索引，0代表第一个
	 */
	public void delete(int index) throws Exception {
		// 先索引到index - 1处
		Node<T> node = head;
		for (int i = -1; i < index - 1; i++) {
			node = node.getNext();
			// 判断是否越界
			if (node.getNext() == null) {
				throw new Exception("插入位置超出范围！");
			}
		}
		// 直接把第index - 1处的节点的下一个指向index + 1处的节点即可
		node.setNext(node.getNext().getNext());
	}

	/**
	 * 修改一个节点内容
	 *
	 * @param index 待修改节点索引
	 * @param data  修改后内容
	 */
	public void set(int index, T data) throws Exception {
		// 索引到index节点
		Node<T> node = head;
		for (int i = -1; i < index; i++) {
			node = node.getNext();
			// 判断是否越界
			if (node == null) {
				throw new Exception("位置超出范围！");
			}
		}
		// 直接修改即可
		node.setData(data);
	}

	/**
	 * 得到指定索引处的节点值
	 *
	 * @param index 指定索引
	 * @return 节点值
	 */
	public T get(int index) throws Exception {
		// 索引到index节点
		Node<T> node = head;
		for (int i = -1; i < index; i++) {
			node = node.getNext();
			// 判断是否越界
			if (node == null) {
				throw new Exception("位置超出范围！");
			}
		}
		// 返回即可
		return node.getData();
	}

	/**
	 * 打印链表
	 */
	public void printLinkedList() {
		Node<T> node = head;
		System.out.print("○");
		while ((node = node.getNext()) != null) {
			System.out.print(" -> " + node.getData());
		}
		System.out.println();
	}

}